#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

https://www.geeksforgeeks.org/shortest-un-ordered-subarray/


朴素解法:
        1. 寻找所有这样的数a, 如果a右边存在比自己小的数b,
          那么a未排序. 所有a的最小索引(最左边)是未排序数组的开端

        2. 对称的: 寻找所有这样的数z, 如果z右边存在比自己大的数x,
          那么z未排序. 所有z的最大索引(最左边)是未排序数组的末端
"""

class Solution:
    def __init__(self):
        pass

    def shortest_unordered_subarray(self, nums):

        left = len(nums)
        find = False
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] > nums[j]:
                    left_idx = i
                    find = True
                    break

            if find:
                break

        right = -1
        find = False
        # for i in range(len(nums-1), -1, -1):
        for i in self.reverse_range( len(nums) ):
            if find:
                break
            for j in range(i-1, -1, -1):
                if nums[j] > nums[i]:
                    right_idx = i
                    find = True
                    break

        return left_idx, right_idx


    def reverse_range(self, num):
        return range(num-1, -1, -1)



def test():
    s = Solution()
    nums = [7, 9, 10, 8, 11]

    left_idx, right_idx = s.shortest_unordered_subarray(nums)
    print(left_idx, right_idx, right_idx-left_idx+1)

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
